Комбинаторный подход к оценке качества обучаемых алгоритмов
Автор: К.В. Воронцов
Источник: Математические вопросы кибернетики / Под ред. О.Б. Лупанов. – М.: Физматлит, 2004. – Том 13, с. 5-36.
Автор: К.В. Воронцов
Источник: Математические вопросы кибернетики / Под ред. О.Б. Лупанов. – М.: Физматлит, 2004. – Том 13, с. 5-36.
The combinatorial theory of machine learning is developed that extends the famous Vapnik-Chervonenkis statistical theory and allows to obtain a new kind of generalization bounds. Combinatorial bounds of cross-validation functionals require no probabilistic assumptions, even no i.i.d. hypothesis. The postulate of uniform convergence also turns out to be redundant. Combinatorial approach allows to more accurately describe the learning process itself and to reveal the effect of algorithms space localization: when a target function is fixed, most learning procedures generate algorithms (functions, concepts) from a small part of algorithms space. Thus the complexity of overall space may have nothing to do with generalization. A new notion of local growth function is introduced to describe this phenomenon. Then a general causes of complexity-based bounds weakness are considered. A new bounds are obtained that do not depend of space complexity but require a priory knowledge about target function. Two types of additional information are considered: compactness of classes and monotonicity or almost-monotonicity of the target function.
Вопрос о качестве алгоритмов, синтезированных по конечным выборкам прецедентов, является фундаментальной проблемой теории обучаемых систем (machine learning theory).
В общем случае задача обучения по прецедентам заключается в том, чтобы по заданной выборке пар «объект-ответ» восстановить функциональную зависимость между объектами и ответами, то есть построить алгоритм, способный выдавать адекватные ответы на предъявляемые объекты. Когда множество допустимых ответов конечно, говорят о задачах классификации или распознавания образов. Когда множество допустимых ответов бесконечно, например, является множеством действительных чисел или векторов, говорят о задачах восстановления регрессии. Когда объекты соответствуют моментам времени, а ответы характеризуют будущее поведение процесса или явления, говорят о задачах прогнозирования.
Значительный опыт решения прикладных задач распознавания, восстановления регрессии и прогнозирования был накоплен уже к середине 60-х годов. Большую популярность приобрёл подход, основанный на построении модели восстанавливаемой зависимости в виде параметрического семейства алгоритмов. С помощью численной оптимизации в семействе выбирался алгоритм, допускающий наименьшее число ошибок на заданной обучающей выборке. Проще говоря, осуществлялась подгонка (fitting) модели под выборку. Этот метод получил название минимизации эмпирического риска.
На практике исследователи столкнулись с проблемой переобучения (overfitting). Чем больше у алгоритма свободных параметров, тем меньшего числа ошибок на обучении можно добиться путём оптимизации. Однако по мере нарастания сложности модели «оптимальные» алгоритмы начинают слишком хорошо подстраиваться под конкретные данные, улавливая не только черты восстанавливаемой зависимости, но и ошибки измерения обучающей выборки, и погрешность самой модели. В результате ухудшается качество работы алгоритма вне обучающей выборки, или, как говорят, его способность к обобщению (generalization performance).
Из этого наблюдения был сделан вывод, что для всякой задачи существует оптимальная сложность модели, при которой достигается наилучшее качество обобщения. Первое формальное обоснование этого практического опыта было дано в статистической теории восстановления зависимостей по эмпирическим данным, разработанной В. Н. Вапником и А. Я. Червоненкисом в конце 60-х — начале 70-х [2, 3].
Статистическая теория Вапника-Червоненкиса. Обобщающая способность определяется как вероятность ошибки алгоритма, полученного в результате обучения, либо как частота его ошибок на некоторой независимой и, вообще говоря, неизвестной контрольной выборке. Далее вводится подходящая мера сложности семейств алгоритмов, называемая ёмкостью или размерностью Вапника-Червоненкиса (VC-dimension). Основным результатом теории являются количественные оценки, показывающие, что качество получаемых алгоритмов улучшается с ростом длины обучающей выборки и уменьшением частоты ошибок на обучении, но ухудшается при увеличении сложности семейства. Эти оценки позволяют обосновать метод структурной минимизации риска (СМР), непосредственно направленный на выбор модели оптимальной сложности. В СМР фиксируется некоторая структура вложенных подсемейств различной сложности, затем в каждом подсемействе решается задача обучения по прецедентам, и из полученных алгоритмов выбирается тот, для которого оценка качества принимает наилучшее значение. Более подробно основные положения статистической теории излагаются в разделе 3.
К сожалению, оценки Вапника-Червоненкиса сильно завышены, что приводит к требованию слишком длинных обучающих выборок (105—106 объектов), а в методе структурной минимизации риска — к чрезмерному упрощению алгоритмов [61]. Некоторые семейства имеют бесконечную ёмкость и находятся за границами применимости теории, тем не менее с их помощью удаётся решать прикладные задачи, и довольно успешно. В частности, это относится к метрическим методам, основанным на явном хранении обучающей выборки, таким как метод ближайших соседей, а также к методам алгебраического подхода [10, 11, 12, 13], гарантирующим безошибочное распознавание заданной выборки. На практике качество обучения почти всегда оказывается существенно лучше, чем предсказывает статистическая теория.
Причина завышенности статистических оценок кроется в их слишком большой общности. Они справедливы при любом распределении вероятностей и любой восстанавливаемой зависимости, следовательно, ориентированы на «худший случай». Они не учитывают важных особенностей самой задачи и процесса поиска её решения, благодаря которым «эффективная» сложность подмножества алгоритмов, реально используемого в данной конкретной задаче, может оказаться существенно меньше сложности всего семейства.
Во-первых, это особенности распределения объектов в пространстве — они могут лежать в подпространстве меньшей размерности. В задачах восстановления зависимостей этот случай является типичным, поскольку наличие зависимых или почти зависимых признаков является скорее правилом, чем исключением.
Во-вторых, это особенности самой восстанавливаемой зависимости — она может быть гладкой, симметричной, монотонной или обладать другими специальными свойствами, что резко сужает пространство поиска решения.
В-третьих, это особенности метода обучения — он может обладать способностью подстраиваться под задачу, выдавая алгоритмы, в некотором смысле похожие на восстанавливаемую зависимость. Различные методы обучения в неравной степени обладают способностью локализовать «эффективное» подсемейство алгоритмов.
Появление статистической теории вызвало большое количество исследований, направленных на уточнение оценок. Однако проблема получения численных оценок, непосредственно применимых на практике, оказалась вызывающе трудной, и до сих пор остаётся открытой.
Далее будут перечислены некоторые направления современных исследований по проблемам обоснования обучаемых алгоритмов и получения оценок качества обучения. Разумеется, предлагаемая классификация весьма условна и не претендует на полноту.
Эффективная сложность. При решении конкретной задачи далеко не каждый алгоритм из выбранного семейства имеет шансы быть полученным в результате обучения. Как правило, реально работает не всё семейство, а лишь небольшая его часть. Этот факт был замечен ещё В. Н. Вапником, предложившим понятие эффективной ёмкости вместе с алгоритмом её практического измерения [87, 38]. Эффективная ёмкость не превосходит полной ёмкости семейства и зависит от выборки. Она учитывает особенности исходного распределения объектов, но не принимает во внимание особенностей восстанавливаемой зависимости и метода обучения. В дальнейшем концепция оценок, зависящих от данных (data dependent bounds), получила развитие во многих работах, см. например, [81, 90, 39, 40, 32].
К этому направлению примыкают также работы В. Л. Матросова, который впервые показал, что при специальном выборе метода обучения возможно обеспечить корректное распознавание любой заданной обучающей выборки, пользуясь подмножеством алгоритмов ограниченной ёмкости [15, 16, 17]. При этом построение алгоритма проводится в алгебраическом расширении семейства алгоритмов вычисления оценок (АВО) [13]. В отличие от стандартного подхода, здесь существенно используются свойства метода обучения, но не учитываются особенности распределения объектов и восстанавливаемой зависимости.
Статья [89] содержит исторический обзор, отражающий процесс постепенного уточнения оценок Вапника-Червоненкиса. Отмечается, что наилучшая оценка, справедливая при самых общих предположениях, получена М. Талаграндом [85]. На её основе выводится новая, несколько более точная, оценка, справедливая при некотором «разумном» ограничении класса вероятностных распределений на множестве исходных объектов.
При использовании оценок, зависящих от данных, метод структурной минимизации риска трансформируется и приводит к построению самоограничивающих алгоритмов (self bounding learning algorithms) [57]. От исходного СМР они отличаются тем, что структура вложенных подсемейств не задаётся заранее, а формируется в процессе обучения. В этом случае оценки качества учитывают все три типа особенностей, упомянутых выше. Результатом обучения является не только сам алгоритм, но и оценка его обобщающей способности. Такая оценка уже не выписывается явно в виде формулы, а вычисляется по ходу построения алгоритма. Наличие оценки качества на каждом промежуточном шаге позволяет эффективно управлять процессом обучения.
Принцип самоограничения алгоритмов применяется также для обоснования стандартных методов построения решающих деревьев [76]. Эти методы основаны на аналогичной стратегии — в ходе построения алгоритма по обучающей выборке происходит последовательное сужение подсемейства алгоритмов, в котором ведётся поиск решения [67].
Граничность объектов. Второе направление связано с понятием отступа или маржи (margin) в задачах классификации с пороговым решающим правилом. Несколько упрощая, можно сказать, что отступ — это расстояние от объекта до границы классов. Если объект относится алгоритмом к чужому классу, то его отступ отрицателен. Чем больше в обучающей выборке объектов с большим отступом, тем лучше разделяются классы, тем надёжнее может быть классификация. Идея уточнения оценок качества заключается в том, чтобы сравнивать вероятность ошибки не с частотой ошибок на обучении, а с долей обучающих объектов, имеющих отрицательный или малый положительный отступ. При этом величина эмпирического риска искусственно завышается, зато вероятность ошибки существенно более точно оценивается по объектам, далеко отстоящим от границы классов.
Подход, основанный на понятии отступа, оказался особенно плодотворным при исследовании линейных пороговых классификаторов, в частности, машин опорных векторов (support vectors machines, SVM) [46, 84] и методов взвешенного голосования [34], о которых пойдёт речь чуть ниже. Он также позволяет обосновать алгоритмы, использующие метрику (функцию расстояния) в пространстве объектов, если предположить, что разделяющая поверхность проходит на достаточном удалении от обучающих объектов [36].
Наиболее ярким конструктивным результатом данного подхода являются методы обучения, направленные на явную максимизацию отступа. Они позволяют строить алгоритмы с лучшей обобщающей способностью, что подтверждается теоретически и экспериментально [69].
С понятием отступа тесно связана ещё одна мера сложности семейства алгоритмов, альтернативная функции роста — fat-размерность (fat-shattering dimension) [63, 33, 29, 32].
Композиционная структура алгоритмов. Третье направление исследований связано с понятием композиции алгоритмов. Во многих прикладных задачах удаётся построить несколько различных алгоритмов, ни один из которых не восстанавливает искомую зависимость достаточно хорошо. Тогда имеет смысл объединить эти алгоритмы с помощью корректирующей операции, в надежде на то, что недостатки одних алгоритмов будут скомпенсированы достоинствами других, и качество композиции окажется лучше, чем качество каждого из базовых алгоритмов в отдельности.
Известно много способов конструирования алгоритмических композиций.
Наиболее общая теория алгоритмических композиций разработана в алгебраическом подходе к построению корректных алгоритмов, предложенном академиком РАН Ю. И. Журавлёвым и активно развиваемом его учениками [10, 11, 12, 13, 9, 25, 6].
В методе Л. А. Растригина пространство объектов разбивается на области компетентности, и для каждой области строится свой алгоритм [18]. Затем эти алгоритмы «склеиваются». Качество такой конструкции определяется качеством отдельных алгоритмов.
Раньше других стали применяться простые процедуры голосования (по большинству, по старшинству, и другие), не имеющие собственных параметров для настройки. Ввиду существенной дискретности они используются, главным образом, при решении задач классификации. Более общая процедура взвешенного голосования (weighted voting) строит выпуклую комбинацию алгоритмов — линейную комбинацию с неотрицательными нормированными весами. Эта процедура обладает существенно большей гибкостью, и её применяют как для классификации, так и для восстановления регрессии. Многие широко известные алгоритмические конструкции явно или не явно используют принцип взвешенного голосования, в частности, нейронные сети, потенциальные функции [1], алгоритмы вычисления оценок [13], и другие.
В работе П. Бартлетта [34] впервые было показано, что эффективная сложность выпуклой комбинации классификаторов равна не суммарной, и даже не максимальной, как ранее предполагалось, а средней взвешенной сложности отдельных классификаторов, взятых с теми же весами, с которыми они входят в комбинацию. Иными словами, взвешенное голосование не увеличивает сложность алгоритма, а лишь сглаживает прогнозы базовых классификаторов. Вытекающие отсюда оценки обобщающей способности существенно точнее классических сложностных оценок Вапника-Червоненкиса, хотя и они всё ещё сильно завышены (требуемая длина обучения имеет порядок 104—105). Этот результат обосновывает ряд эвристических приёмов, направленных на уменьшение весов при настройке нейронных сетей, таких как сокращение весов (weight decay) и ранний останов (early stopping).
Результаты, первоначально полученные для линейных комбинаций, оказались применимы и к более широкому классу алгоритмов. В частности, бинарные решающие деревья и дизъюнктивные нормальные формы допускают представление в виде выпуклой комбинации булевых функций с пороговым решающим правилом [58]. Получены оценки обобщающей способности и для более сложных алгоритмических композиций, представимых в виде пороговых выпуклых комбинаций над пороговыми выпуклыми комбинациями. Примерами таких конструкций являются сигмоидальные нейросети с одним скрытым уровнем и взвешенное голосование решающих деревьев [70]. Для всех этих случаев оценки обобщающей способности выражаются через долю обучающих объектов с малым отступом.
Для успешной коррекции необходимо, чтобы базовые алгоритмы достаточно сильно различались. Если алгоритмы строятся независимо друг от друга, возникает опасность, что некоторые из них окажутся одинаковыми или почти одинаковыми. Существуют специальные техники, направленные на увеличение различий между базовыми алгоритмами.
В методе баггинга (bagging — сокращение от «bootstrap aggregation»), предложенном Л. Брейманом [43, 44, 45], производится взвешенное голосование базовых алгоритмов, обученных на различных подвыборках данных, либо на различных частях признакового описания объектов. Выделение подмножеств объектов и/или признаков производится, как правило, случайным образом.
Метод бустинга (boosting) Р. Френда и И. Шапира [56, 53, 80] также является разновидностью взвешенного голосования, но базовые алгоритмы строятся последовательно, и процесс увеличения различий между ними управляется детерминированным образом. А именно, для каждого базового алгоритма, начиная со второго, веса обучающих объектов пересчитываются так, чтобы он точнее настраивался на тех объектах, на которых чаще ошибались все предыдущие алгоритмы. Веса алгоритмов также вычисляются исходя из числа допущенных ими ошибок.
Идея последовательной компенсации ошибок предыдущих алгоритмов реализована также в оптимизационных (проблемно-ориентированных) методах алгебраического подхода [19, 5, 5]. В отличие от бустинга, здесь используется не выпуклая комбинация, а более сложная корректирующая операция в виде нелинейной монотонной функции достаточно общего вида. Монотонность можно рассматривать как обобщение выпуклости: любая выпуклая корректирующая операция является монотонной, обратное в общем случае неверно. При выпуклой коррекции вес каждого базового алгоритма остается постоянным на всем пространстве объектов, что представляется не вполне обоснованной эвристикой. Монотонная коррекция обладает существенно более богатыми возможностями для настройки. С другой стороны, для монотонных корректирующих операций, как для более широкого семейства функций, существенно выше опасность переобучения.
Обобщающая способность бустинга исследована, пожалуй, наиболее хорошо. Во многих случаях экспериментально наблюдается почти неограниченное улучшение качества обучения при наращивании числа алгоритмов в композиции [54]. Более того, качество на тестовой выборке может продолжать улучшаться даже после достижения безошибочного распознавания обучающей выборки. Эти наблюдения противоречат непосредственным выводам статистической теории, основанным на анализе сложности.
Существует несколько объяснений феноменов бустинга. С одной стороны, бу-стинг активно максимизирует отступы обучающих объектов, и продолжает «раздвигать классы» даже после достижения корректности на обучении [79]. С другой стороны, бустинг строит выпуклую комбинацию вещественнозначных классификаторов, которая проявляет свойство стабильности (см. ниже) [52].
Имеется много работ по сравнительному анализу обобщающей способности бу-стинга и баггинга. Баггинг направлен исключительно на уменьшение вариации (variance) модели, в то время как бустинг способствует уменьшению и вариации, и смещения (bias) [55]. Эмпирические исследования [83] на 4 реальных задачах показывают, что бустинг работает лучше на больших обучающих выборках, баггинг — на малых. При увеличении длины выборки бустинг повышает разнообразие классификаторов активнее, чем баггинг. Наконец, бустинг лучше воспроизводит границы классов сложной формы.
Работы Бартлетта, Френда, Шапира и др. решительным образом изменили представления о соотношении качества и сложности. Если ранее считалось, что для надёжного восстановления зависимости необходимо ограничивать сложность используемого семейства алгоритмов, то теперь исследователи приходят к выводу, что семейство может быть сколь угодно сложным, однако первостепенную роль играет метод обучения — тот способ, с помощью которого по обучающей выборке строится алгоритм из выбранного семейства. По всей видимости, некоторые разновидности взвешенного голосования, такие как бустинг, являются «удачными» методами, способными эффективно сужать изначально широкое семейство алгоритмов, подстраивать его под конкретную задачу.
Стабильность. Следующее, четвёртое, направление исследований связано с понятием стабильности (stability) [41, 42, 66]. Метод обучения называется стабильным, если небольшие вариации обучающей выборки, такие как вставка или удаление одного объекта, приводят к незначительным изменениям получаемого алгоритма. Существуют различные способы формального определения стабильности, например, в работе [66] вводится 12 различных определений и устанавливаются взаимосвязи между ними. Как правило, оценки качества стабильных методов не зависят от сложностных характеристик семейства. В частности, получены оценки стабильности и обобщающей способности локальных методов типа ближайших соседей и потенциальных функций [78, 49, 50]. Эти методы широко используются благодаря своей простоте, однако порождают семейства алгоритмов бесконечной ёмкости. Доказана стабильность бустинга, машин опорных векторов, методов минимизации эмпирического риска с регуляризирующей штрафной функцией, и некоторых других. К сожалению, численные оценки требуемой длины обучения для стабильных методов также сильно завышены, как сложностные, и дают только качественное обоснование соответствующих алгоритмов.
Концентрация вероятности. Современные исследования таких свойств обучаемых алгоритмов, как эффективная сложность, отступ, композиционная структура и стабильность, существенно опираются на современный математический аппарат, описывающий явление концентрации вероятностной меры (measure concentration). В первых работах Вапника и Червоненкиса для этого использовались классические неравенства Хёфдинга и Берншнейна. Более точные результаты удаётся получать с помощью неравенств Чернова [47], метода ограниченных разностей МакДиарми-да [72] и изопериметрических неравенств Талагранда [85, [86]. Вводное изложение этих математических техник можно найти в обзорах [31].
Скользящий контроль. Ещё одно направление исследований связано с использованием скользящего контроля (cross-validation) [51 ,[65].
Процедура скользящего контроля заключается в следующем. Фиксируется некоторое множество разбиений исходной выборки на две части: обучающую и контрольную. Для каждого разбиения выполняется настройка алгоритма по обучающей под-выборке и вычисляется частота его ошибок на контрольной подвыборке. Оценка скользящего контроля определяется как средняя по всем разбиениям частота ошибок на контроле. Фактически, скользящий контроль непосредственно измеряет обобщающую способность метода обучения на заданной конечной выборке.
В зависимости от способа формирования множества разбиений различают несколько разновидностей скользящего контроля [65]. Если множество разбиений одноэлементно, говорят об оценке качества на отдельной тестовой выборке (hold-out estimate). Если используются все разбиения с контрольной выборкой единичной длины, то говорят об оценке с одним отделяемым объектом (leave-one-out estimate, LOO). Если используются все разбиения с контрольной выборкой фиксированной, но не обязательно единичной, длины, то говорят об оценке полного скользящего контроля (complete cross-validation) [74]. Если генерируется случайное подмножество разбиений с контрольной выборкой фиксированной длины, то говорят о бутстреп-оценке (bootstrap estimate) [28]. Если множество разбиений образуется k непересекающи-мися контрольными выборками, в объединении дающими всю исходную выборку, то говорят о k-кратном скользящем контроле (k-fold cross-validation).
Несмотря на известную громоздкость, в некоторых случаях техника скользящего контроля непосредственно приводит к простым изящным результатам. В частности, для машин опорных векторов доказано, что LOO не превосходит доли опорных векторов во всей выборке. В силу несмещённости LOO отсюда немедленно вытекает, что вероятность ошибки не превосходит математического ожидания доли опорных векторов [48]. На практике частота ошибок на контроле часто оказывается ещё в несколько раз меньше.
При исследовании локальных методов обучения использование функционала LOO становится естественной «вынужденной мерой» из-за очевидной смещённости эмпирического риска. В частности, для метода первого ближайшего соседа частота ошибок на обучении всегда равна нулю. Начиная с работ Девроя, Роджерса, Вагнера [78, 49, 50] функционал LOO остаётся одним из основных инструментов исследования стабильности методов обучения.
На практике скользящий контроль чаще всего применяется либо для выбора одной модели алгоритмов из нескольких (model selection) [64], либо для оптимизации небольшого числа параметров, определяющих структуру алгоритма, таких, как степень полинома, параметр регуляризации или количество нейронов на скрытом уровне нейронной сети. Считается, что настройка значительной доли параметров по скользящему контролю лишена смысла. Когда контрольная выборка существенно вовлекается в процесс обучения, скользящий контроль начинает выдавать смещённую заниженную оценку обобщающей способности. Причиной является всё та же переподгонка, которая приводит к заниженности эмпирического риска [75]. Известно, что скользящий контроль даёт несмещённую оценку вероятности ошибки в том случае, когда он используется для проверки качества по окончании обучения. Однако до сих пор нет исчерпывающих исследований, показывающих, в какой степени скользящий контроль может использоваться на стадии обучения.
Интуиция подсказывает, что скользящий контроль должен характеризовать обобщающую способность алгоритма лучше, чем частота ошибок на обучении. Тем не менее, этот факт долгое время не удавалось доказать. Попытки предпринимались неоднократно [64, 62, 59], но были получены лишь «разумные» верхние границы (sanity-check bounds) для отклонения скользящего контроля от вероятности ошибок алгоритма. Указанные оценки даже несколько хуже, чем оценки Вапника-Червоненкиса для отклонения эмпирического риска.
Причина этих неудач анализируется в [37], где вводятся и сравниваются два альтернативных способа формализации понятия обобщающей способности. При первом способе, близком к подходу Вапника-Червоненкиса, оценивается качество отдельного алгоритма, полученного в результате обучения. Это приводит к завышенным оценкам, зависящим от ёмкости семейства и требующим дополнительных предположений о стабильности метода обучения [62]. При втором способе оценивается качество метода обучения в целом. Оказывается, в этом случае оценка отклонения скользящего контроля от вероятности ошибки алгоритма, обученного на случайной выборке, не зависит от ёмкости семейства, а только от длины обучения и контроля. Данный результат проясняет природу скользящего контроля и показывает, что завышенность предыдущих оценок связана с неудачным выбором функционала качества.
Отсюда вытекают два важных вывода.
Во-первых, теория качества обучения может оказаться весьма чувствительной к исходной аксиоматике, в частности, к формализации самого понятия качества обучения.
Во-вторых, скользящий контроль характеризует обобщающую способность метода не намного хуже, чем вероятность ошибки. Наиболее точное выражение эти идеи нашли в комбинаторном подходе к обоснованию обучаемых алгоритмов, развиваемом в настоящей работе.
Комбинаторный подход возник как попытка более точного построения статистической теории Вапника-Червоненкиса, начиная с исходных её постулатов. Для этого имелось две основные предпосылки.
Первой предпосылкой было понимание того, что обобщающую способность целесообразно определять как частоту ошибок на конечной контрольной выборке, но не как вероятность ошибки, которая является величиной ненаблюдаемой, и которую невозможно вычислить точно. На практике любая обучаемая система сталкивается только с конечными выборками, будь то обучающие, контрольные или рабочие совокупности объектов. Использование гипотетических вероятностей может приводить (и реально приводит — см. «основную лемму» [3], стр. 219) к лишним промежуточным шагам при доказательстве оценок и понижению их точности.
Второй предпосылкой было понимание того, что принцип минимизации эмпирического риска в заранее заданном семействе алгоритмов не достаточно точно описывает процесс обучения. На практике всегда используется конкретная процедура обучения, которая по заданной обучающей выборке строит единственный алгоритм, совсем не обязательно минимизирующий эмпирический риск.
В комбинаторном подходе явным образом вводится понятие метода обучения, по отношению к которому семейство алгоритмов становится вторичной конструкцией. Это позволяет рассматривать любые методы, а не только минимизацию эмпирического риска. Качество обучения по прецедентам (обобщающая способность метода) характеризуется комбинаторными функционалами, основанными на принципе скользящего контроля, и зависящими только от метода обучения и заданной конечной выборки. В данной работе изучается несколько разновидностей функционала полного скользящего контроля. Соответствующие определения вводятся в разделе 4.
Верхние оценки комбинаторных функционалов аналогичны по своей структуре статистическим, но вместо сложности всего семейства в них фигурирует сложность локального подсемейства, состоящего из алгоритмов, которые могут быть выданы методом обучения в данной конкретной задаче. Наибольший интерес представляет случай, когда локальная сложность оказывается существенно меньше сложности всего семейства.
Комбинаторные оценки, полученные в разделе 5, справедливы для любого метода обучения и любой конечной выборки, не обязательно случайной, независимой, одинаково распределённой. Эти оценки выводятся комбинаторными методами без использования теории вероятностей. Оценки стандартных вероятностных функционалов оказываются непосредственным следствием комбинаторных. Это означает, что при переходе от статистической теории к комбинаторной соблюдается «принцип соответствия», а проблема качества обучения имеет скорее комбинаторную, чем вероятностную природу. Комбинаторная перестройка аксиоматики приводит к пересмотру многих положений статистической теории, некоторые из которых рассматриваются в разделах 7, 8, 9, 10.
В разделе 11 указываются три основные причины завышенности сложностных оценок качества. Наиболее существенной из них представляется погрешность, неизбежно возникающая при оценивании качества через сложность. Она связана с самой структурой сложностных оценок и присуща как вероятностным, так и комбинаторным оценкам. Две другие причины завышенности удаётся устранить с помощью комбинаторного подхода.
Универсальные ограничения. Ввиду принципиальной завышенности слож-ностных оценок можно выдвинуть предположение, что получить приемлемые численные результаты возможно только путём явного привлечения априорной информации о восстанавливаемой зависимости. Основная идея этого направления состоит в том, что если метод обучения строит алгоритмы, в некотором смысле «согласованные» с имеющейся априорной информацией, то для такого метода может существовать оценка обобщающей способности, существенно лучшая, чем в общем случае.
Отметим, что соответствие обучающей выборки (локальной информации) и априорных ограничений (универсальной информации) подробно изучается в теории универсальных и локальных ограничений К. В. Рудакова [20, 23, 21, 22, 24, 9] с позиций теории категорий и алгебраического подхода к проблеме распознавания. Алгебраическая теория позволяет проверять непротиворечивость этих двух типов информации и конструктивно описывать неизбыточные классы моделей алгоритмов, допускающие построение корректных алгоритмов. Однако оценки обобщающей способности в данной теории не рассматриваются. Вообще, проблема влияния априорной информации на качество восстановления зависимости представляется наименее изученной. В настоящей работе получены два результата в этом направлении.
В разделе 12 рассматривается метод ближайшего соседа в сочетании с априорной информацией о компактности классов. Полученное выражение функционала качества является точным и не зависит от сложностных характеристик семейства, которое, как известно, имеет бесконечную ёмкость.
В разделе 13 рассматривается класс методов, строящих монотонные алгоритмы, в сочетании с априорной информацией о монотонности или почти-монотонности восстанавливаемой зависимости. Соответствующая оценка качества также не зависит от сложности семейства, которое также имеет бесконечную ёмкость. Она является существенно более точной на малых выборках, чем оценки, полученные ранее другими авторами [27, 82].
В разделе 14 перечисляются некоторые проблемы, остающиеся открытыми в комбинаторном подходе.
Дополнением к приведённому выше обзору является периодически пополняемая частично аннотированная библиографическая база MachLearn, размещённая по адресу www.ccas.ru/frc. Настоящая работа содержит все доказательства, опущенные в кратком сообщении [7].
Получение оценок качества лишено смысла, если они не способствуют совершенствованию применяемых на практике алгоритмов.
Ожидается, что оценка (14) позволит обосновать критерии оптимизации метрик для методов типа ближайших соседей или потенциальных функций, основанных на анализе сходства объектов. В частности, представляется возможной разработка методов комбинирования некорректных эвристических метрик путём явной оптимизации профиля компактности.
Ожидается, что оценка (16) позволит обосновать проблемно-ориентированные методы монотонной коррекции [6]. Открытой проблемой остаётся теоретическое и/или эмпирическое сравнение монотонной и выпуклой коррекции (в частности, бу-стинга) с точки зрения их обобщающей способности.
Ограничения компактности и монотонности — далеко не единственные «разумные» виды априорной информации. Остаётся открытым вопрос о получении не-сложностных оценок при априорных ограничениях иного вида.
Пока не ясно, существуют ли нетривиальные оценки локальной функции роста для конкретных методов обучения. Различные методы, работающие в одном и том же семействе, могут порождать различные локальные подсемейства на различных классах задач. Отсюда вытекает целесообразность введения и исследования нового понятия — локализирующей способности метода обучения, как важной составляющей его обобщающей способности.
Возможен пересмотр не только теории равномерной сходимости, но и других техник, используемых для анализа качества обучения, с позиций комбинаторного (частотного) подхода. Теоретико-вероятностные предположения представляются избыточными не только в рассмотренном случае, но также при анализе стабильности, отступа и структуры алгоритмических композиций.
Важной проблемой представляется исследование границ применимости скользящего контроля на стадии построения алгоритма, в частности, при выборе наилучшего метода обучения из заданного конечного набора методов.
Автор выражает глубокую признательность академику РАН Ю. И. Журавлёву за оказываемую поддержку и своему Учителю чл.-корр. РАН К. В. Рудакову за постоянное внимание к работе и ценные замечания.
Работа выполнена в рамках программы Отделения математических наук РАН «Алгебраические и комбинаторные методы математической кибернетики», поддержана Российским фондом фундаментальных исследований (проекты № 02-01-00325, № 01-07-90242) и Фондом содействия отечественной науке.